本题是三倍经验 Link1 Link2,不知道为啥这几题难度评分不一样,区别只有多组数据和模数。
好了,下面进入正题。
题意简述:多组数据,给定 ,求 的所有排列中逆序对个数恰有 个的情况。
由于有多组数据,因此考虑预处理出所有情况后进行 查询,虽然这题数据范围较小好像也不用。
怎么进行预处理呢?考虑进行动态规划。
设计状态 表示对于 的所有排列,恰有 个逆序对的情况总数。
考虑如何进行转移。我们在 的一个排列,添加一个数 ,此时我们可以使逆序对个数增加 个。因此,我们可以得到转移方程:
此时,根据我们状态的定义, 即为所求。
这是我们注意到一个问题:这个转移是 的,无法通过上面两道双倍经验,因此需要优化。
看到我们最后一维要加的是一个区间内的 值,容易想到通过维护前缀和来优化时间。我们采取循环中滚动求前缀和的方式。
代码中的前缀和开的是数组,也有只用一个变量的做法(其实并不难),因为我懒,这里就不写了。
另外,由于数量可能很大,需要开 long long。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1005;
ll T, n, m;
ll dp[N][N] = {{0}, {1}}, s[N];
void dpInit() {
for(ll i=2;i<=1000;i++) {
memset(s, 0, sizeof(s));
for(ll j=0;j<=1000;j++) {
s[j] = dp[i-1][j];
if(j) s[j] += s[j-1];
dp[i][j] = s[j];
ll _ = j - i + 1;
if(_ >= 0) s[j] -= dp[i-1][_];
}
}
}
int main() {
dpInit();
scanf("%lld", &T);
while(T--) {
scanf("%lld%lld", &n, &m);
printf("%lld\n", dp[n][m]);
}
return 0;
}